Hai nước đã thiết lập quan hệ ngoại giao vào 1954.[1] Mặc dù Mông Cổ không trực tiếp tham gia chiến tranh Việt Nam, nhưng họ vẫn bày tỏ sự ủng hộ về ý thức hệ đối với Bắc Việt Nam bằng cách hỗ trợ tương tự trong Thế chiến II cho Liên Xô và chiến tranh Triều Tiên với Bắc Triều Tiên, và cung cấp vật nuôi như là sự hỗ trợ vật chất, bao gồm nhiều hơn hơn 100.000 đầu ngựa, bò và cừu. Sau chiến tranh, Mông Cổ đã tiếp nhận và nuôi dưỡng hơn 400 trẻ em mồ côi chiến tranh trong những năm 1960-1970 ,. Lãnh đạo Bắc Việt Hồ Chí Minh đã đến thăm Mông Cổ và bày tỏ sự đánh giá cao sự hỗ trợ của Mông Cổ trong thời chiến; Nhà lãnh đạo Mông Cổ Yumjaagiin Tsedenbal đã có chuyến thăm đối ứng tới Hà Nội vào cuối năm đó. Vào thời điểm đó, hai nước đã ký Hiệp định Hợp tác Kinh tế và Văn hóa và năm sau bắt đầu tiến hành thương mại song phương. Các nước đã ký Hiệp ước hữu nghị và hợp tác vào năm 1961, đổi mới năm 1979 và ký kết một hiệp ước mới vào năm 1995. Vào ngày 13 tháng 1 năm 2003, các nước đã ký một văn bản hợp tác 8 điểm cam kết hợp tác giữa hai chính phủ và các cơ quan lập pháp của họ, thay thế một tài liệu trước đó được ký vào năm 1998.

Đã có 13 phiên họp của ủy ban liên chính phủ Việt Nam-Mông Cổ về hợp tác thương mại, kinh tế và khoa học công nghệ, với phiên họp tiếp theo sẽ được tổ chức tại Ulaanbaatar vào năm 2010 . Vào ngày 25 tháng 5 năm 2004 tại Ulaanbaatar, các nước đã ký thỏa thuận về vận tải đường sắt và hợp tác khoa học và công nghệ. Các thỏa thuận khác đã bao gồm các lĩnh vực như bảo vệ thực vật và các quy định kiểm dịch, hải quan, y tế và giáo dục.